No description has been provided for this image

M2.992 · Anàlisi de xarxes complexes

20251 - Màster universitari en Ciència de dades (Data science)

Estudis d'Informàtica, Multimèdia i Telecomunicacions

 
Nom i cognoms: Marc Cervera Rosell
Recordatori: Verificació d'autoria mitjançant entrevista de contrast Aquesta activitat està subjecta a la verificació de l'autoria, la qual pot incloure entrevistes de contrast, tal com es descriu en el pla docent de l'assignatura. En cas que el professorat ho consideri necessari, es podrà convocar l'estudiant per realitzar una entrevista amb l'objectiu de comprovar la correspondència entre el contingut presentat i els coneixements adquirits, així com l'autoria independent de l'activitat. Trobareu més informació en el pla docent de l'assignatura..

Fonts bibliogràfiques i ús d’eines d’IA. És necessari que l’estudiant indiqui totes les fonts que ha utilitzat per a l’elaboració dels diferents apartats de la PAC i de quina manera han estat utilitzades. Això inclou qualsevol ús d’eines d’IA generativa o similars, les quals estan permeses. No indicar de manera adequada els recursos utilitzats pot ser considerat plagi i penalitzat amb un suspens (D).
Figures i representacions gràfiques Les figures han de contenir sempre una etiqueta i ser degudament clares i informatives. Si no es compleixen aquestes condicions, les representacions, quan es demanin, es consideraran completament incorrectes. Algunes guies o exemples sobre com han de ser les figures:
  • https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4161295/
  • https://www.quanthub.com/designing-charts-axes-and-value-labels/

Disenyar i representar de forma correcta informació gràfica és una competència transversal que s'ha d'adquirir.

Alguns punts fonamentals:

  • LLegendes clares i informatives incloent-hi les seves unitats.
  • El format de les línies, punts i representacions gràfiques ha de ser tan informatiu i clar com sigui possible.
  • Els textos superposats sobre altres textos o sobre informació gràfica es puntuarà, en general, de manera molt negativa.
Puntualitat en el lliurament de la PAC Les PAC lliurades més enllà de la data límit (fins i tot amb minuts de retard) seran avaluades com a entregues realitzades en avaluació extraordinària. Es recomana, per tant, fer el lliurament amb prou antelació per prevenir possibles problemes tècnics d’última hora amb l’exportació del document, problemes de connexió, etc.

PEC 3: Xarxes Complexes¶

En aquesta pràctica revisarem els conceptes apresos en els mòduls 1, 2 i 3 i seguirem introduint més nivells de complexitat realistes en l'anàlisi de xarxes complexes, tal i com recullen els materials del mòdul 4.

Les competències que es treballaran en aquesta activitat són les següents:

  1. Aprofundir en la comprensió de les propietats de les xarxes complexes que s’observen en dades empíriques.
  2. Aprofundir en els models de fluxos d’informació en el context de la propagació epidèmica.
  3. Conèixer i implementar models de contagi complex en el context de xarxes amb interaccions d’alt ordre.
  4. Conèixer i implementar algoritmes per analitzar xarxes temporals.
  5. Aprofundir en la comprensió de les dinàmiques de xarxa a diferents escales, tant per als estats dels nodes com per a l’evolució dels enllaços.

Consideracions generals:

  • Aquesta prova d’avaluació s’ha de resoldre utilitzant la biblioteca NetworkX i les altres biblioteques importades en l’enunciat. L’ús de qualsevol altra biblioteca s’ha de justificar dins de la mateixa activitat.
  • Aquesta PEC s’ha de realitzar de manera estrictament individual. Qualsevol indici de còpia serà penalitzat amb un suspens (D) per a totes les parts implicades i pot comportar l’avaluació negativa de l’assignatura de manera íntegra.
  • És necessari que l’estudiant indiqui totes les fonts que ha utilitzat per a la realització de la PEC. En cas contrari, es considerarà que l’estudiant ha comès plagi, i serà penalitzat amb un suspens (D) i la possible avaluació negativa de l’assignatura de manera íntegra.

Format del lliurament:

  • Alguns exercicis poden requerir diversos minuts d’execució, per la qual cosa el lliurament s’ha de fer en format notebook i en format HTML, on s’hi vegi el codi, els resultats i els comentaris de cada exercici. Es pot exportar el notebook a HTML des del menú File → Download as → HTML.
  • Hi ha un tipus de cel·la especial per incloure text. Aquest tipus de cel·la us serà molt útil per respondre les diferents preguntes teòriques plantejades al llarg de l’activitat. Per canviar el tipus de cel·la, aneu al menú: Cell$\to$ Cell Type $\to$ Markdown.

Càrrega de llibreries¶

En la següent cel·la s’han de carregar totes les llibreries necessàries per a l’execució de l’activitat. Cal justificar l’ús de qualsevol llibreria addicional que no formi part del conjunt bàsic requerit.

In [1]:
# Llibreries bàsiques
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

# Llibreries addicionals (justificar el seu ús)

Les versions de les llibreries que es recomanen per a aquesta activitat són les següents. No és necessari utilitzar aquestes llibreries, però són les que s’han utilitzat per provar la solució.

  • NetworkX ver. 3.2.1
  • Pandas ver. 2.2.3
  • Numpy ver. 1.26.4
In [2]:
# Comprovar les versions
print("NetworkX ver. {}".format(nx.__version__))
print("Pandas ver. {}".format(pd.__version__))
print("Numpy ver. {}".format(np.__version__))
NetworkX ver. 3.2.1
Pandas ver. 2.2.3
Numpy ver. 1.26.4

Xarxa Multilacapa de "Game of Thrones" (6,5 punts)¶

Aquest primer exercici se centra en l’estudi de les interaccions dels personatges d’una de les sèries de televisió més populars dels darrers anys. Ens referim a "Game of Thrones", l’adaptació televisiva de la saga de novel·les riu "Cançó de Gel i Foc" de George R.R. Martin.

En el següent enllaç trobaràs les dades que utilitzarem per treballar en aquest exercici, les quals determinen les interaccions dels personatges de la sèrie per a les diferents temporades, així com l’explicació del que representen aquestes interaccions: https://github.com/mathbeveridge/gameofthrones/tree/master

Comencem.

Exercici 1: Importació de les dades (0,25 punts)

Importa les dades generant els grafs per a cada capa, i obtén el nombre de nodes i arestes per a cadascuna d’elles. (0,25 punts)

Nota: En cas que hi hagi un node en l’arxiu d’arestes que no aparegui en el d’arxius de nodes, s’ha d’afegir.

Solució
In [3]:
import csv # Per crear un csv_reader i usar la funció next() per saltar les capçaleres # Bibliografia: [Ref.1]
def create_graph_of_season(nodes, edges):
    graph = nx.Graph()
    # -- Afegir nodes --
    with open(nodes) as f:
        csv_reader = csv.reader(f) # Bibliografia: [Ref.1]
        header = next(csv_reader) # Bibliografia: [Ref.1]
        for line in csv_reader:
            id_character = line[0].strip()
            label_character = line[1].strip()
            graph.add_node(id_character, label=label_character) # Bibliografia: [Ref.2]
    f.close()
    current_nodes = list(graph.nodes()) # Per a comprovar si falta algun node (no esta aquí però sí a les arestes) # Bibliografia: [Ref.3]
    # -- Afegir arestes --
    with open(edges) as f:
        csv_reader = csv.reader(f) # Bibliografia: [Ref.1]
        header = next(csv_reader) # Bibliografia: [Ref.1]
        for line in csv_reader:
            source = line[0].strip()
            target = line[1].strip()
            weight = int(line[2].strip())
            season = line[3].strip()
            if source not in current_nodes:
                graph.add_node(source, label=source.capitalize()) # Bibliografia: [Ref.4]
                current_nodes = list(graph.nodes())
            if target not in current_nodes:
                graph.add_node(target, label=target.capitalize()) # Bibliografia: [Ref.4]
                current_nodes = list(graph.nodes())
            graph.add_edge(source, target, weight=weight, season=season)
    f.close()
    return graph
In [4]:
# -- Season 1 --
nodes_s1 = "gameofthrones/data/got-s1-nodes.csv"
edges_s1 = "gameofthrones/data/got-s1-edges.csv"
graph_s1 = create_graph_of_season(nodes_s1, edges_s1)
num_nodes_s1 = len(list(graph_s1.nodes()))
num_edges_s1 = len(list(graph_s1.edges()))
In [5]:
# -- Season 2 --
nodes_s2 = "gameofthrones/data/got-s2-nodes.csv"
edges_s2 = "gameofthrones/data/got-s2-edges.csv"
graph_s2 = create_graph_of_season(nodes_s2, edges_s2)
num_nodes_s2 = len(list(graph_s2.nodes()))
num_edges_s2 = len(list(graph_s2.edges()))
In [6]:
# -- Season 3 --
nodes_s3 = "gameofthrones/data/got-s3-nodes.csv"
edges_s3 = "gameofthrones/data/got-s3-edges.csv"
graph_s3 = create_graph_of_season(nodes_s3, edges_s3)
num_nodes_s3 = len(list(graph_s3.nodes()))
num_edges_s3 = len(list(graph_s3.edges()))
In [7]:
# -- Season 4 --
nodes_s4 = "gameofthrones/data/got-s4-nodes.csv"
edges_s4 = "gameofthrones/data/got-s4-edges.csv"
graph_s4 = create_graph_of_season(nodes_s4, edges_s4)
num_nodes_s4 = len(list(graph_s4.nodes()))
num_edges_s4 = len(list(graph_s4.edges()))
In [8]:
# -- Season 5 --
nodes_s5 = "gameofthrones/data/got-s5-nodes.csv"
edges_s5 = "gameofthrones/data/got-s5-edges.csv"
graph_s5 = create_graph_of_season(nodes_s5, edges_s5)
num_nodes_s5 = len(list(graph_s5.nodes()))
num_edges_s5 = len(list(graph_s5.edges()))
In [9]:
# -- Season 6 --
nodes_s6 = "gameofthrones/data/got-s6-nodes.csv"
edges_s6 = "gameofthrones/data/got-s6-edges.csv"
graph_s6 = create_graph_of_season(nodes_s6, edges_s6)
num_nodes_s6 = len(list(graph_s6.nodes()))
num_edges_s6 = len(list(graph_s6.edges()))
In [10]:
# -- Season 7 --
nodes_s7 = "gameofthrones/data/got-s7-nodes.csv"
edges_s7 = "gameofthrones/data/got-s7-edges.csv"
graph_s7 = create_graph_of_season(nodes_s7, edges_s7)
num_nodes_s7 = len(list(graph_s7.nodes()))
num_edges_s7 = len(list(graph_s7.edges()))
In [11]:
# -- Season 8 --
nodes_s8 = "gameofthrones/data/got-s8-nodes.csv"
edges_s8 = "gameofthrones/data/got-s8-edges.csv"
graph_s8 = create_graph_of_season(nodes_s8, edges_s8)
num_nodes_s8 = len(list(graph_s8.nodes()))
num_edges_s8 = len(list(graph_s8.edges()))
In [12]:
print("---------------------------------------- Temporada 1 ----------------------------------------")
print(f"Nodes de la temporada 1: {num_nodes_s1}")
print(f"Arestes de la temporada 1: {num_edges_s1}\n")
print("---------------------------------------- Temporada 2 ----------------------------------------")
print(f"Nodes de la temporada 2: {num_nodes_s2}")
print(f"Arestes de la temporada 2: {num_edges_s2}\n")
print("---------------------------------------- Temporada 3 ----------------------------------------")
print(f"Nodes de la temporada 3: {num_nodes_s3}")
print(f"Arestes de la temporada 3: {num_edges_s3}\n")
print("---------------------------------------- Temporada 4 ----------------------------------------")
print(f"Nodes de la temporada 4: {num_nodes_s4}")
print(f"Arestes de la temporada 4: {num_edges_s4}\n")
print("---------------------------------------- Temporada 5 ----------------------------------------")
print(f"Nodes de la temporada 5: {num_nodes_s5}")
print(f"Arestes de la temporada 5: {num_edges_s5}\n")
print("---------------------------------------- Temporada 6 ----------------------------------------")
print(f"Nodes de la temporada 6: {num_nodes_s6}")
print(f"Arestes de la temporada 6: {num_edges_s6}")
print("---------------------------------------- Temporada 7 ----------------------------------------")
print(f"Nodes de la temporada 7: {num_nodes_s7}")
print(f"Arestes de la temporada 7: {num_edges_s7}\n")
print("---------------------------------------- Temporada 8 ----------------------------------------")
print(f"Nodes de la temporada 8: {num_nodes_s8}")
print(f"Arestes de la temporada 8: {num_edges_s8}")
---------------------------------------- Temporada 1 ----------------------------------------
Nodes de la temporada 1: 126
Arestes de la temporada 1: 549

---------------------------------------- Temporada 2 ----------------------------------------
Nodes de la temporada 2: 129
Arestes de la temporada 2: 486

---------------------------------------- Temporada 3 ----------------------------------------
Nodes de la temporada 3: 124
Arestes de la temporada 3: 504

---------------------------------------- Temporada 4 ----------------------------------------
Nodes de la temporada 4: 172
Arestes de la temporada 4: 667

---------------------------------------- Temporada 5 ----------------------------------------
Nodes de la temporada 5: 119
Arestes de la temporada 5: 396

---------------------------------------- Temporada 6 ----------------------------------------
Nodes de la temporada 6: 142
Arestes de la temporada 6: 541
---------------------------------------- Temporada 7 ----------------------------------------
Nodes de la temporada 7: 81
Arestes de la temporada 7: 412

---------------------------------------- Temporada 8 ----------------------------------------
Nodes de la temporada 8: 74
Arestes de la temporada 8: 553

Referències externes:

[Ref.1] -- How to Skip CSV Headers in Python: Process Data From Row 2 Without Editing Headers [en línia] [consulta: 30 de novembre de 2025]. Disponible a: https://www.pythontutorials.net/blog/how-to-skip-the-headers-when-processing-a-csv-file-using-python/#method-1-using-pythons-built-in-csv-module --> Web que explica com ignorar les capçaleres del fitxer csv.

[Ref.2] -- Graph.add_node [en línia] [consulta: 30 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.add_node.html --> Documentació ofical de la funció per a afegir nodes a un graf.

[Ref.3] -- Graph.nodes [en línia] [consulta: 30 de novembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.nodes.html --> Documentació oficial de la funció per a obtenir els nodes d'un graf.

[Ref.4] -- Python String capitalize() Method [en línia] [consulta: 30 de novembre de 2025]. Disponible a: https://www.w3schools.com/python/ref_string_capitalize.asp --> Web que explica com posar la primera lletra d'un string en majúscula i la resta en minúscula.

Exercici 2: Visualització del graf (0,75 punts)

La Figura 9 de l’article “A survey of community detection methods in multilayer networks” de Xinyu Huang i al. (2021), mostra una visualització de la xarxa multilayer de Joc de Trons, que conté les cinc primeres temporades. Basant-te en aquesta visualització, et demanem que en realitzis una de nova millorada que inclogui les vuit temporades.

Nota: Pots obtenir l’article en el següent enllaç: https://link.springer.com/article/10.1007/s10618-020-00716-6

Solució
In [13]:
# --- Aquest exercici ha estat resolt amb l'ajuda de [Ref.5] -> Ús 1 ---
got_dict = {1: graph_s1, 2: graph_s2, 3: graph_s3, 4: graph_s4, 5: graph_s5, 6: graph_s6, 7: graph_s7, 8: graph_s8} # {temporada: graf}
multilayer_got = nx.Graph()
for graph in got_dict.values(): # El compose() uneix tots els grafs de les temporades en un de sol -> Representa la info de tota la sèrie
    multilayer_got = nx.compose(multilayer_got, graph) # Bibliografia: [Ref.6]
base_pos = nx.spring_layout(multilayer_got, k=3) # Bibliografia: [Ref.7]
layer_offset = {season: season * 3.0 for season in got_dict.keys()} # Per a que no es superposin els grafs de les temporades
# -- Càlcul posicions de cada capa --
layer_positions = {}
for character, (coord_x, coord_y) in base_pos.items():
    for season in got_dict:
        layer_positions[(character, season)] = (coord_x + layer_offset[season], coord_y)
# -- Construcció del graf multilayer per visualitzar --
got_multilayer_plot = nx.Graph()
for season, graph in got_dict.items():
    for character in graph.nodes():
        got_multilayer_plot.add_node((character, season))
# -- Connexions --
for season, graph in got_dict.items():
    for character_1, character_2, args in graph.edges(data=True):
        weight = args["weight"]
        got_multilayer_plot.add_edge((character_1, season), (character_2, season), weight=weight)
# -- Connexions entre capes --
for character in multilayer_got.nodes():
    for season in range(1, 8):
        if character in got_dict[season] and character in got_dict[season + 1]:
            got_multilayer_plot.add_edge((character, season), (character, season + 1))
# -- Visualització --
plt.figure(figsize=(100,100))
# - Dibuix connexions de cada capa -
for season in got_dict.keys():
    edges = [edge for edge in got_multilayer_plot.edges() if edge[0][1] == season and edge[1][1] == season]
    nx.draw_networkx_edges(got_multilayer_plot, layer_positions, edgelist=edges, edge_color='r') # Bibliografia: [Ref.8]
# - Dibuix connexions entre capes -
interlayer_edges = [edge for edge in got_multilayer_plot.edges() if edge[0][1] != edge[1][1]]
nx.draw_networkx_edges(got_multilayer_plot, layer_positions, edgelist=interlayer_edges, edge_color='b') # Bibliografia: [Ref.8]
# - Dibuix nodes -
nx.draw_networkx_nodes(got_multilayer_plot, layer_positions, node_size = 200, node_color='k') # Bibliografia: [Ref.9]
plt.axis("off") # Bibliografia: [Ref.10]
plt.title("Xarxa multicapa de la sèrie Joc de trons. Cada capa de la xarxa és una temporada de la sèrie", fontsize=90)
plt.show()
No description has been provided for this image
-------------------------------------------- Adquisició de coneixement de la creació assistida per IA de la figura de l'exerici 2 --------------------------------------------

El graf got_dict enllaça cada nombre de temporada amb el seu graf corresponent de l'exercici 1. Aquest diccionari serà d'utilitat en moments com la unificació dels grafs de les 8 temporades en 1 sol graf que contingui tota la informació de la sèrie o el càlcul de les posicions de cada capa en el dibuix final.

El graf multilayer_got actúa com "el tot", és a dir és l'univers sencer de Joc de Trons (és el model de dades complet de les 8 temporades). Aquest graf es crea a partir de la composició dels grafs de cada temporada.

Un cop obtingut el graf de l'univers de Joc de trons, es calcula la posició dels nodes d'aquest graf per a que puguin ser visualitzats. En aquest cas, s'utilitza la funció spring_layout() per a calcular la posició dels nodes. Aquesta funció utilitza l'algorisme force-directed de Fruchterman-Reingold per a obtenir les coordenades de posició dels diferents nodes. El problema d'aquest càlcul és que si s'utilitzen aquestes coordenades per fer la visualització, les diferents capes es dibuixaràn superposades entre elles, per tant, s'aplica un offset de 3.0 (3.0 * nombre_de_temporada) (a l'eix X) per tal de desplaçar les diferents capes i que no es superposin les unes amb les altres. Un cop obtingut el desplaçament de cada capa, s'aplica als personatges.

Seguidament, s'inicialitza el graf que s'utilitzarà per a la visualització i s'afegeixen els nodes de cada temporada en format (personatge, temporada) per tal d'identificar a quina temporada correspon cada personatge.

Amb els nodes afegits, el següent pas es afegir les arestes. Tant aquelles que relacionen personatges en una temporada concreta, com aquelles que relacionen el personatge amb si mateix a la següent temporada (en cas de que el personatge aparegui en la següent temporada). Per afegir les arestes que relacionen personatges en una temporada concreta, es comproben els grafs del diccionari que relaciona una temporada amb un graf i s'afegeixen les arestes corresponents a cada temporada.

Per afegir les arestes entre capes, es comproba, en el graf "univers" si els personatges en una temporada $t$ apareixen a la temporada $t+1$. En cas de ser aixi s'afegeix una aresta entre el personatge que està situat a la capa de la temporada $t$ i ell/ella mateix a la temporada $t+1$.

En aquest punt, l'única cosa que queda per fer es construir la figura. En primer lloc, es dibuixen aquelles arestes que no es mouen de capa, és a dir, aquelles arestes que relacionen personatges en una temporada concreta. Per saber si una aresta relaciona dos personatges en una temporada concreta, es comproba la llista d'arestes del graf de la visualització i per cada parell de tuples en format (personatge, temporada) es comproba que el valor de temporada sigui el mateix.

Per dibuixar les arestes que relacionen personatges entre capes es segueix el mateix procediment que per a les arestes dins de cada capa però en aquest cas es comproba que el valor de temporada sigui diferent.

Finalment s'afegeixen els nodes, es treuen els eixos (perquè en aquest cas no tenen sentit) i s'aplica un títol al graf.

Per tant, l'aprenentatge extret d'aquest exercici assistit per IA és que a l'hora de representar visualment un graf multicapa, cal construirlo pas a pas. És a dir, cal calcular "l'univers" que representa tota la informació i amb aquest "univers" calcular la posició de cada capa. Un cop fet aquest treball "global" cal construir el graf multicapa que s'utilitzarà per a la visualització. Aquest és el que s'ha de construir per passos. El primer pas es saber els nodes de cada capa (tot i que s'afegeixen tots els nodes de cop però es poden diferenciar les capes degut al format (nom_node, capa)). Finalment calcalcular per separat les arestes de cada capa i les arestes que "viatgen" d'una capa a la següent.

Referències externes:

[Ref.5] -- OPENAI. ChatGPT [programari].GPT-5.2025

Ús 1 --> Ajuda a la resolució de l'exercici 2 de l'apartat de Xarxes multicapa.

Ús 2 --> Ajuda per a establit un titol a la figura que conté 8 subfigures (2 files de 4 subfigures cadascuna).

Ús 3 --> Utilitzat per la gestio de valors propis 0.

Ús 4 --> Utilitzat per seleccionar els 20 personatges amb més centralitat de vectors propis.

[Ref.6] -- compose [en línia] [consulta: 2 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.operators.binary.compose.html --> Documentació oficial de la funció per a fusionar dos grafs en un.

[Ref.7] -- spring_layout [en línia] [consulta: 2 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.drawing.layout.spring_layout.html --> Documentació oficial de la funció per a calcular la posició dels nodes d'un graf mitjançant l'algorisme force-directed de Fruchterman-Reingold.

[Ref.8] -- draw_networkx_edges [en línia] [consulta: 2 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw_networkx_edges.html --> Documentació oficial de la funció per a dibuixar les arestes d'un graf.

[Ref.9] -- draw_networkx_nodes [en línia] [consulta: 2 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw_networkx_nodes.html --> Documentació oficial de la funció per a dibuixar els nodes d'un graf.

[Ref.10] -- matplotlib.pyplot.axis [en línia] [consulta: 2 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.axis.html --> Documentació oficial de la funció per a manipular els eixos d'una figura.

Exercici 3: Anàlisi intracapa de la xarxa (2,5 punts)

3.1) Comencem amb les distribucions de grau de cada capa. En aquest sentit, realitza una visualització que les mostri i analitza els resultats obtinguts. (0,75 punts)

3.2) L’article de Domenico et al. (2015) "Structural reducibility of multilayer networks" planteja una metodologia que permet quantificar la redundància estructural d’un graf multilayer, i un dels procediments inclosos en aquesta metodologia és l’entropia de Von Neumann. En aquest sentit et demanem que:

3.2.1) Basant-te en l’article, explica amb les teves paraules com s’obté l’Entropia de Von Neumann i elabora el codi per poder obtenir-la per a cada capa del graf d’aquest exercici. (1 punt)

3.2.2) Aplica el codi obtingut en l’apartat anterior per a cada temporada, mostra els resultats de manera clara en una visualització i analitza’ls amb les teves paraules. (0,75 punts)

Nota: Pots obtenir l’article en el següent enllaç: https://www.nature.com/articles/ncomms7864

------------------------------------------------------------------------------------- Exercici 3.1 -------------------------------------------------------------------------------------
In [14]:
# -- Obtenció dels graus --
degrees_seasons = {} # Per guardar cada DegreeView amb la seva temporada
for season, graph_season in got_dict.items():
    degrees_seasons[season] = graph_season.degree() # Bibliografia: [Ref.11]

# -- Representació dels graus -- # Bibliografia: [Ref.12]
fig, ax = plt.subplots(2, 4, figsize=(15,15))
fig.suptitle("Distribució de graus de les 8 temporades de Joc de Trons") # Bibliografia: [Ref.13] i [Ref.5] -> Ús 2
k = 1
for i in range(2):
    for j in range(4):
        degree_view = degrees_seasons[k]
        degrees = [degree for character, degree in degree_view]
        ax[i, j].hist(degrees, edgecolor='black', bins=20) # Bibliografia: [Ref.14] i [Ref.15]
        ax[i, j].set_title(f"Distribució de graus de la temporada {k}", fontsize=10) # Bibliografia: [Ref.16]
        ax[i, j].set_ylabel("Freqüència") # Bibliografia: [Ref.17]
        ax[i, j].set_xlabel("Graus") # Bibliografia: [Ref.18]
        k += 1
plt.show()
No description has been provided for this image
Solució 3.1 Les distribucions de grau de les 8 capes de la xarxa mostren un patró comú entre elles. En totes les temporades es pot observar que els graus baixos són predominants. Això significa que una gran part dels personatges (nodes) tenen poques interaccions mentre que els personatges amb graus més elevats són pocs. Els personatges amb més grau, són aquells que tenen més interaccions. Si s'extrapola aquest fet a la sèrie, es pot veure que els personatges amb més interaccions són els personatges principals, mentre que els personatges amb menys interaccions (i, per tant, menys grau) són els personatges secundaris.

També es pot observar que a mesura que la sèrie avança, hi ha una certa tendència a què els graus mitjans i més elevats tinguin una freqüència més gran, però els graus més baixos continuen dominant.

------------------------------------------------------------------------------------ Exercici 3.2.1 ------------------------------------------------------------------------------------
Solució 3.2.1 L'obtenció de l'entropia de Von Neuman d'una xarxa multicapa s'obté com la suma de l'entropia de Von Neuman de cadascuna de les capes de la xarxa multicapa.

Per obtenir l'entropia d'una capa cal, en primer lloc, calcular la matriu laplaciana combinatòria associada al graf. Aquesta matriu s'obté com a resultat de $(D - A)$ on $D$ és la matriu diagonal dels graus dels nodes i $A$ és la matriu d'adjacència del graf.

Un cop obtinguda aquesta matriu, se li ha d'aplicar un factor de reescalat $c$ que es defineix com la inversa del doble del nombre d'arestes, és a dir: $c = 1 / (2 * nombre\_arestes)$. Per aplicar aquest factor de reescalar, l'única cosa que cal fer es multiplicar la matriu laplaciana per aquest factor (matriu * nombre = multiplicar cada element de la matriu pel nombre).

Un cop reescalada la matriu, es calculen els valors propis de la matriu resultant. Els valors propis el logaritme dels quals tendeix a infinit (logaritmes de 0) s'han descartat per evitar errors de càlcul.

Finalment, es realitza la suma dels productes de cada valor propi multiplicat pel logaritme en base 2 de cada valor propi. Un cop s'ha sumat s'aplica el signe "-".

In [15]:
from numpy import linalg
def von_neuman_entropy(graph):
    laplacian = nx.laplacian_matrix(graph).toarray() # Bibliografia: [Ref.19]
    num_edges = graph.number_of_edges() # Bibliografia: [Ref.20]
    c = 1 / (2 * num_edges) # Factor de reescalat matriu laplaciana
    laplacian_rescaled = c * laplacian
    eigenvalues = linalg.eigvalsh(laplacian_rescaled) # Bibliografia: [Ref.21]
    eigenvalues_non_zero = np.array([eigval for eigval in eigenvalues if eigval > 1e-12]) # Bibliografia: [Ref.5] -> Ús3
    entropy = -np.sum(eigenvalues_non_zero * np.log2(eigenvalues_non_zero))
    return entropy
------------------------------------------------------------------------------------ Exercici 3.2.2 ------------------------------------------------------------------------------------
In [16]:
entropy_layer_1 = von_neuman_entropy(graph_s1)
print(f"Entropia de la capa 1: {entropy_layer_1}\n")
entropy_layer_2 = von_neuman_entropy(graph_s2)
print(f"Entropia de la capa 2: {entropy_layer_2}\n")
entropy_layer_3 = von_neuman_entropy(graph_s3)
print(f"Entropia de la capa 3: {entropy_layer_3}\n")
entropy_layer_4 = von_neuman_entropy(graph_s4)
print(f"Entropia de la capa 4: {entropy_layer_4}\n")
entropy_layer_5 = von_neuman_entropy(graph_s5)
print(f"Entropia de la capa 5: {entropy_layer_5}\n")
entropy_layer_6 = von_neuman_entropy(graph_s6)
print(f"Entropia de la capa 6: {entropy_layer_6}\n")
entropy_layer_7 = von_neuman_entropy(graph_s7)
print(f"Entropia de la capa 7: {entropy_layer_7}\n")
entropy_layer_8 = von_neuman_entropy(graph_s8)
print(f"Entropia de la capa 8: {entropy_layer_8}\n")
total_entropy = entropy_layer_1 + entropy_layer_2 + entropy_layer_3 + entropy_layer_4 + entropy_layer_5 + entropy_layer_6 + entropy_layer_7 
+ entropy_layer_8
print(f"Entropia total de la xarxa multicapa: {total_entropy}\n")
Entropia de la capa 1: 23.406369015172377

Entropia de la capa 2: 26.992283435648897

Entropia de la capa 3: 28.253890466790462

Entropia de la capa 4: 27.95984797306804

Entropia de la capa 5: 26.038524822433

Entropia de la capa 6: 28.94300152889199

Entropia de la capa 7: 17.80187171391072

Entropia de la capa 8: 15.969990324452684

Entropia total de la xarxa multicapa: 179.39578895591546

In [17]:
entropies = [entropy_layer_1, entropy_layer_2, entropy_layer_3, entropy_layer_4, entropy_layer_5, entropy_layer_6, entropy_layer_7,
             entropy_layer_8]
labels_visualization = ["Entropy layer 1", "Entropy layer 2", "Entropy layer 3", "Entropy layer 4", "Entropy layer 5", "Entropy layer 6",
                        "Entropy layer 7", "Entropy layer 8", ]
plt.figure(figsize=(20,20))
plt.barh(labels_visualization, entropies) # Bibliografia: [Ref.22]
plt.title("Entropies de les capes de la xarxa multicapa de Joc de Trons", fontsize=20)
plt.ylabel("Entropia per capes", fontsize=15)
plt.xlabel("Valor de l'entropia", fontsize=15)
plt.locator_params(axis='x', nbins=20) # Bibliografia: [Ref.23]
plt.grid()
plt.show()
No description has been provided for this image
Solució 3.2.2

En l'article s'explica que un graf es troba en estat pur si i només si té una sola aresta, cosa que es correspon amb una entropia de Von Neuman = 0.

Per tant, el primer que es pot observar és que cap capa es troba en estat pur, ja que cap té una entropia igual a 0. És a dir, totes les capes es troben en estat mixt. Cosa que indica que totes les capes tenen més d'una aresta.

S'observa que les capes 3, 4 i 6 són les que tenen l'entropia més elevades (prop de 28 en el cas de la capa 4 i més de 28 en el cas de les capes 3 i 6). Per tant, es pot afirmar que les capes 3, 4 i 6 són les capes mes barrejades. És a dir, són les capes més complexes o més caòtiques.

Les capes 7 i 8 són les capes amb menys entropia. La qual cosa indica grafs més senzills o menys caòtics.

La capa 6 és la capa amb més entropia (28.94) i la capa 8 és la capa amb menys entropia (15.96).

Referències externes:

[Ref.11] -- Graph.degree [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.degree.html --> Documentació oficial de la funció que permeto obtenir el grau d'un graf.

[Ref.12] -- Create multiple subplots using plt.subplots [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/gallery/subplots_axes_and_figures/subplots_demo.html --> Documentació per representar multiples subfigures en una graella.

[Ref.13] -- matplotlib.pyplot.suptitle [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.suptitle.html --> Documentació de la funció per afegir un super títol a la figura.

[Ref.14] -- Tipos de Gráficas: Cuál usar según los datos [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://uni.edu.gt/noticias/tipos-de-graficas/ --> Web que explica els usos de cada gràfic.

[Ref.15] -- matplotlib.pyplot.hist [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.hist.html --> Documentació de la funció per a dibuixar un histograma.

[Ref.16] -- matplotlib.axes.Axes.set_title [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.set_title.html#matplotlib.axes.Axes.set_title --> Documentació de la funció per afegir un títol a un eix concret.

[Ref.17] -- matplotlib.axes.Axes.set_ylabel [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.set_ylabel.html --> Documentació de la funció per a afegir un títol l'eix y.

[Ref.18] -- matplotlib.axes.Axes.set_xlabel [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.set_xlabel.html --> Documentació de la funció per a afegir un títol l'eix x.

[Ref.19] -- laplacian_matrix [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/generated/networkx.linalg.laplacianmatrix.laplacian_matrix.html --> Documentació oficial de la funció per a calcular la matriu laplaciana d'un graf.

[Ref.20] -- Graph.number_of_edges [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.number_of_edges.html --> Documentació oficial de la funció per a obtenir el nombre d'arestes d'un graf.

[Ref.21] -- numpy.linalg.eigvalsh [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://numpy.org/doc/stable/reference/generated/numpy.linalg.eigvalsh.html#numpy.linalg.eigvalsh --> Documentació oficial de la funció per a calcular els valors propis d'una matriu.

[Ref.22] -- matplotlib.pyplot.barh [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://matplotlib.org/stable/api/_as_gen/matplotlib.pyplot.barh.html --> Documentació oficial per a dibuixar un gràfic de barres horitzontals.

[Ref.23] -- Matplotlib.pyplot.locator_params() in Python [en línia][consulta: 4 de desembre de 2025]. Disponible a: https://www.geeksforgeeks.org/python/matplotlib-pyplot-locator_params-in-python/ **--> Web utilitzada per a saber com controlar el comportament de les etiquetes dels eixos. **

Exercici 4: Análisi intercapa de la xarxa (3 punts)

4.1) Comencem aquest estudi determinant el nivell d’estabilitat estructural, és a dir, la centralitat dels nodes del graf multicapa al llarg de les diferents temporades. Mostra-ho amb una visualització que sigui clara i raona els resultats obtinguts. (1,25 punts)

Nota: Per realitzar aquest exercici, revisa els apunts i llegeix aquest article complementari, la cita del qual també trobaràs als apunts: “The structure and dynamics of multilayer networks” de Boccaletti et al. (2014). El pots obtenir en aquest enllaç: https://www.sciencedirect.com/science/article/pii/S0370157314002105

4.2) Per acabar amb la breu anàlisi intercapa, estudia la robustesa de la xarxa multicapa mitjançant la percolació intercapa dirigida per grau agregat, comparant-la amb una eliminació aleatòria de nodes. Realitza una visualització que mostri les corbes que relacionin el % de nodes de la component gegant i el % de nodes eliminats, i ressalta els punts crítics de cadascuna d’elles. Què observes? (1,75 punts)

------------------------------------------------------------------------------------- Exercici 4.1 -------------------------------------------------------------------------------------
In [18]:
# -- Càlcul de centralitats --
centralities = {}
for season, graph_season in got_dict.items():
    centralities[season] = nx.eigenvector_centrality(graph_season, weight='weight') # Bibliografia: [Ref.24]
In [19]:
# -- Representació --
import seaborn as sns # Per fer la representació de les centralitats
data = pd.DataFrame(centralities)
data.fillna(0, inplace=True) # Si un personatge no apareix en una temporada -> 0  # Bibliografia: [Ref.25]
# - Com hi ha molts personatges, només es mostraran el top 30 de personatges amb més centralitat per tal de fer la visualització més senzilla -
# - Selecció dels 30 personatges amb més centralitat realitzada amb l'ajuda de  # Bibliografia: [Ref.5] -> Ús 4 -
data["sum_centralities"] = data.sum(axis=1) # Bibliografia: [Ref.26]
top = data.sort_values("sum_centralities",ascending=False).head(30) # Bibliografia: [Ref.27]
top.drop(columns="sum_centralities", inplace=True)  # Bibliografia: [Ref.28]

plt.figure(figsize=(20,20))
sns.heatmap(top, linewidths=0.5, annot=True) # Bibliografia: [Ref.29]
plt.show()
No description has been provided for this image
Interpretació dels valors de centralitat de vectors propis dels 20 personatges amb major centralitat

# Bibliografia: [Ref.30] --> Ha servit per tenir una manera pràctica de com interpretar els valors de la centralitat de vectors pròpis.

El mapa de calor anterior mostra com a mesura que la centralitat augmenta el color amb el qual es pinta la cèl·la, per a un personatge i temporada concrets, també és més clar. Al contrari que quan la centralitat disminueix. Aleshores, el color cada cop s'apropa més al negre.

Personatges com Tyrion, Cersei i Sansa son personatges que mantenen una centralitat bastant estable i elevada al llarg de tota la sèrie menys en una temporada. En el cas de Tyrion i Cersei la temporada 6 és en la que tenen menys centralitat i en el cas de Sansa és la temporada 5. Per tant, aquests són els personatges influents al llarg de tota la sèrie

Altres personatges, com Ned, Robert i Catelyn tenen una centralitat molt elevada en les primeres temporades (en el cas de Ned i Robert tenen una centralitat molt elevada només en la primera temporada), és a dir, al principi de la sèrie són molt influents i tal com avança la sèrie van perdent centralitat, degut a que perden importància en la història o moren.

També hi ha el cas contrari. Personatges que al principi de la sèrie tenen poca o gens influència en la història (centralitat baixa) i tal com avançen les temporades, la centralitat creix i amb ella la seva influència en la història de la sèrie. Alguns personatges que es troben en aquesta categoría són: Brienne, Tormund, Jorah, o Davos.

També es troben personatges que tenen una centralitat baixa durant tota la sèrie. Això indica que són poersonatges que tenen poca influència en la trama de la sèrie. Alguns personatges del top 20 que es trobarien en aquesta categoría serien: Loras, Grey Worm, Missandey, Pycelle o Hound.

Finalment, hi ha el cas de personatges com Littlefinger, Jon o Jorah que tenen una gran fluctuació en les seves centralitats. És a dir, poden tenir molta influència en la sèrie en una temporada concreta i perdre tota la influència (centralitat baixa) en una o dues temporades per a després tornar a guanyar influència en la historia (centralitat alta un altre cop).

IMPORTANT: Cal tenir en compte que per a poder realitzar una visualització clara i senzilla (amb el posterior anàlisi) només s'han inclòs en la visualització els 30 personatges amb una major centralitat de vectors propis agregada al llarg de les temporades.

------------------------- Adquisició de coneixement de la selecció dels 20 personatges amb més centralitat de vectors propis assistida per IA ------------------------ El coneixement que s'extreu de la part de selecció dels 20 personatges amb més centralitat de vectors pròpis (selecció que ha estat guiada per IA) és que per obtenir els personatges que volemm, cal calcular la mètrica la centralitat total de cada personatge mitjançant la suma de les centralitats de cada temporada(capa). Un cop obtinguda aquesta suma, es poden ordenar les dades i extreure'n la quantitat d'elles que es vulgui. En aquest cas 20.
------------------------------------------------------------------------------------- Exercici 4.2 -------------------------------------------------------------------------------------
In [20]:
# Bibliografia: [Ref.31] -> Ús 1
# Claus en l'explicació de [Ref.31] -> Ús 1:
    # 1. Grau agregat = suma de graus en les capes
    # 2. Percolació -> Eliminar nodes per veure com es fragmenta la xarxa
    # 3. Percolació dirigida per grau i intercapa:
        # 3.1. Els personatges amb mes grau agregat son els primers a ser eliminats.
        # 3.2. En cas de que sigui un dels nodes a eliminar -> cal eliminarlo de totes les capes perquè estem mirant la robustesa de la xarxa
# Passos a seguir segons les claus de les explicacions de [Ref.31] -> Ús 1 i enunciat:
    # Pas 1 --> Calcular graus agregats
    # Pas 2 --> Ordenar els graus agregats de major a menor
    # Pas 3 --> Aplicar percolació
        # Pas 3.1 --> Eliminar el personatge que toqui de la llista de personatges amb grau agregat ordenat (totes les tempordes)
        # Pas 3.2 --> Per cada personatge eliminat --> +1 node eliminat
        # Pas 3.3 --> Calcul component gegant
        # Pas 3.4 --> Calcul de percentatges

# -- Agregació de graus --
agreggated_degrees = {} # Diccionari per guardar parelles "personatge : grau"
for season, graph in got_dict.items():
    for character in graph.nodes():
        agreggated_degrees[character] = agreggated_degrees.get(character, 0) + graph.degree(character, weight='weight') # Bibliografia: [Ref.32]
# Per resoldre aquest exercici cal usar el graf multicapa no les capes per separat. El graf multicapa s'ha creat a l'exercici 2 -> got_multilayer_plot
# -- Ordenat dels personatges per grau --
characters_ordered_percolation = sorted(agreggated_degrees.keys(), key=lambda item:item[1], reverse=True) # Bibliografia: [Ref.33]

# -- Percolació dirigida --
total_nodes = len(got_multilayer_plot.nodes()) # Nombre de nodes totals
directed_percolation_percentage_nodes_removed = []
directed_percolation_percentage_nodes_giant_component = []
percolation_graph = got_multilayer_plot.copy() # Usar una còpia per no trencar el de la visualització
deleted_nodes = 0 # Per calcular el % de nodes eliminats

for character_ordered in characters_ordered_percolation:
    # - Elimincació de personatges al llarg de les temporades -
    for character, season in list(percolation_graph.nodes()):
        if character == character_ordered:
            percolation_graph.remove_node((character, season)) # Bibliografia: [Ref.34]
            deleted_nodes += 1
    # - Càlcul de la component gegant -
    if len(percolation_graph.nodes()) > 0: # Si no hi ha nodes el max() peta
        len_giant_component = len(max(nx.connected_components(percolation_graph), key=len)) # Bibliografia: [Ref.35]
        percentage_removed_nodes = deleted_nodes / total_nodes # Percentatge de nodes eliminats
        percentage_nodes_giant_component = len_giant_component / total_nodes # Percentatge de nodes de la component gegant
        directed_percolation_percentage_nodes_removed.append(percentage_removed_nodes)
        directed_percolation_percentage_nodes_giant_component.append(percentage_nodes_giant_component)
In [21]:
import random # Per fer la ordenació aleatòria dels nodes per la percolació aleatòria
# -- Percolació random --
total_nodes = len(got_multilayer_plot.nodes()) # Nombre de nodes totals
random_percolation_percentage_nodes_removed = []
random_percolation_percentage_nodes_giant_component = []
random_percolation_graph = got_multilayer_plot.copy() # Usar una còpia per no trencar el de la visualització
deleted_nodes = 0 # Per calcular el % de nodes eliminats
# - En comptes d'ordenar per grau agregat -> Ordenació random - # Bibliografia: [Ref.36]
random_order = list(got_multilayer_plot.nodes())
random.shuffle(random_order)

for character_ordered in random_order:
    random_percolation_graph.remove_node(character_ordered)
    deleted_nodes += 1
    # - Càlcul component gegant -
    if len(random_percolation_graph.nodes()) > 0: # Si no hi ha nodes el max peta -> El if es necessàri
        len_giant_component = len(max(nx.connected_components(random_percolation_graph), key=len))
        percentage_removed_nodes = deleted_nodes / total_nodes
        percentage_nodes_giant_component = len_giant_component / total_nodes
        random_percolation_percentage_nodes_removed.append(percentage_removed_nodes)
        random_percolation_percentage_nodes_giant_component.append(percentage_nodes_giant_component)
In [22]:
plt.figure(figsize=(20,20))
plt.plot(directed_percolation_percentage_nodes_removed, directed_percolation_percentage_nodes_giant_component, label="Directed percolation")
plt.plot(random_percolation_percentage_nodes_removed, random_percolation_percentage_nodes_giant_component, label="Random percolation")
plt.title("Percentatge de nodes eliminat vs. Percentatge de nodes de la component gegant després d'un procés de percolació", fontsize=20)
plt.xlabel("Percentatge de nodes eliminats", fontsize=15)
plt.ylabel("Percentatge de nodes de la component gegant", fontsize=15)
plt.locator_params(axis='x', nbins=30)
plt.grid()
plt.legend()
plt.show()
No description has been provided for this image
Observació del gràfic de percolacions

Es pot observar que la corba corresponent a la percolació aleatòria (taronja) tendeix a decreixer més ràpidament que la corba blava (percolació dirigida) a partir d' un percentatge de nodes eliminats d'entre 0.45 i 0.5 més o menys. És a dir, la corba taronja, amb un menor percentatge de nodes eliminats, tendeix a tenir un menor percentatge de nodes a la component gegant.

També s'observa que quan el percentatge de nodes eliminats es baix (fins a 0.45 més o menys), el comportament d'ambdues corbes és molt similar. És a dir que totes dues corbes tendeixen a tenir un percentatge de nodes molt similar a la component gegant per al mateix pecentatge de nodes eliminats. Tot i que s'observa que la corba blava, corresponent a la percolació dirigida, en quasi tot aquest tram, va per sota de la corba taronja (aleatòria). Això indica que la component gegant de la percolació dirigida es menor que la de la percoalció aleatòria en aquest tram. Per tant, en aquest tram de fins a un percentatge de 0.45 (45%) de nodes eliminats, s'observa que l'eliminació de nodes amb grau elevat afecta més quan la percolació és dirigida.

L'últim tram del gràfic, mostra el cas contrari (a partir de 45% de nodes eliminats). La corba taronja (percolació aletòria) disminueix més ràpidament que la corba de la percolació dirigida (blau). Fet que indica que en aquest tram final, l'eliminació aleatòria de nodes afecta més a la xarxa.

Finament, es pot observar que quan el percentatge de nodes eliminats és d'un 46%/48% més o menys, es quan la tendència de les corbes canvia. És a dir a partir d'aquest percentatge es quan la corba taronja disminueix més ràpidament.

Referències externes:

[Ref.24] -- eigenvector_centrality [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.eigenvector_centrality.html#networkx.algorithms.centrality.eigenvector_centrality --> Documentació oficial per a calcular la centralitat de vectors propis d'un graf.

[Ref.25] -- Eigenvector Centrality [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://www.sciencedirect.com/topics/computer-science/eigenvector-centrality --> Recull de diferents papers que parlen de la centralitat de valors propis.

[Ref.26] -- pandas.DataFrame.sum [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.sum.html --> Documentació oficial per a realitzar suma de valors en un dataframe de Pandas.

[Ref.27] -- pandas.DataFrame.sort_values [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.sort_values.html --> Documentació oficial de la funció per a ordenar valors en un dataframe de Pandas.

[Ref.28] -- pandas.DataFrame.drop [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.drop.html --> Documentació oficial de la funció per a eliminar files o columnes d'un dataframe de Pandas.

[Ref.29] -- seaborn.heatmap [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://seaborn.pydata.org/generated/seaborn.heatmap.html --> Documentació oficial de la funció per a crear un mapa de calor.

[Ref.30] -- Eigenvector centrality [en línia][consulta: 7 de desembre de 2025]. Disponible a: https://en.wikipedia.org/wiki/Eigenvector_centrality --> Pàgina de Wikipedia que dóna informació sobre la Eigenvector centrality.

[Ref.31] -- GOOGLE. Gemini [programari]. Flash 2.5. 2024

Ús 1 --> Utilitzat perquè expliqui amb detall el concepte "percolacio intercapa dirigida per grau agregat".

Ús 2 --> S'ha demanat una explicació senzilla de simplex2.

Ús 3 --> S'ha demanat ajuda per corregir l'afegit de triangles, ja que anteriorment no s'assegurava que s'afegissin triangles en tots els casos.

Ús 4 --> Introducció de correccions atès que els gràfics es veuen malament.

[Ref.32] -- Python Dictionary get() Method [en línia][consulta: 8 de desembre de 2025]. Disponible a: https://www.w3schools.com/python/ref_dictionary_get.asp --> Web que explica com utilitzar la funció get().

[Ref.33] -- Sort Python Dictionary by Key or Value - Python [en línia][consulta: 8 de desembre de 2025]. Disponible a: https://www.geeksforgeeks.org/python/python-sort-python-dictionaries-by-key-or-value/ --> Web que explica diferents mètodes d'ordenació de diccionaris.

[Ref.34] -- Graph.remove_node [en línia][consulta: 8 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.remove_node.html --> Documentació oficial de la funció per a eliminar un node d'un graf.

[Ref.35] -- BERMOLEN, Paola. Teoría Básica de Grafos [en línia]. Monteviedo: Udelar, 2022 [consulta: 8 de desembre de 2025]. Disponible a: https://eva.fing.edu.uy/pluginfile.php/486297/mod_label/intro/2_teoria_grafos_handout.pdf --> Recurs d'aprenentatge de la facultat d'enginyeria de la Universitat de la República d'Uruguay sobre teoría de grafs.

[Ref.36] -- Python Random shuffle() Method [en línia]. Monteviedo: Udelar, 2022 [consulta: 8 de desembre de 2025]. Disponible a: https://www.w3schools.com/python/ref_random_shuffle.asp --> Web que explica com utilitzar la funció shuffle().

Complexos Simplicials en contagis socials (3,5 punts)¶

L’article “Simplicial models of social contagion” de Iacopini et al. (2019) introdueix una metodologia per a l’estudi de processos de contagi que va més enllà de les interaccions binàries —els grafs simples— incorporant interaccions d’ordre superior mitjançant complexos simplicials.

Aquest article serà la base d’aquest segon i darrer exercici, en què et demanem que recreïs la Figura 3 d’aquest article, la qual mostra la dinàmica del model implementat (SCM o Simplicial Contagion Model), sobre un Complex Simplicial Aleatori (Random Simplicial Complex o RSC). Som-hi.

Nota: Pots obtenir l’article en el següent enllaç: https://www.nature.com/articles/s41467-019-10431-6

Exercici 1: Model SCM sobre un RSC (1,25 punts)

Basant-te en l’article en qüestió, elabora el codi que permeti executar l’SCM sobre un RSC amb els mateixos paràmetres que els d’aquest article. Comprova el model obtingut imprimint resultats d’algun paràmetre i/o executant una simulació curta.

Solució
In [23]:
# graph -> Graf d'estudi RSC
# beta1 -> Probabilitat d'infecció 1-simplex -> simplex-1 = Procés estocàstic 1
# beta2 -> Probabilitat infecció 2-simplex -> simplex-2 = Procés estocàstic 2
# mu -> Probabilitat de recuperació
# initial_infected -> Percetntatge d'infectats incials (assignar random)
# time_steps -> les diferents "t".
# Decisió contagi -> "[...]an individual is simultaneously exposed to multiple sources of contagion[...]" -> Prob. combinada P(simplex-1 o simplex2)
# P(simplex-1 o simplex2) = 1 - P(no simplex-1 y no simplex2) [Truco Ref.37] -> 
# P(no simplex-1 y no simplex2) = P(no simplex-1) * P(no simplex2) [Ref.38] i [Ref.39]
# P(no simplex-1) * P(no simplex2) = (1 - P(simplex-1)) * (1 - P(simplex-2)) [Ref.39] ==>
# P(simplex-1 o simplex2) = 1 - [(1 - P(simplex-1)) * (1 - P(simplex-2))]
# 1 - P(simplex-1) = 1 - beta1
# 1 - P(simplex-2) = 1 - beta2
# Bibliografia: [Ref.37] i [Ref.38] i [Ref.39]
def find_triangles_s2(graph):
    triangles = []
    for clique in nx.find_cliques(graph): # Bibliografia: [Ref.40]
        if len(clique) == 3:
            triangles.append(clique)
    return triangles

def scm_order_2(graph, beta1, beta2, mu, initial_infectious=0.1, time_steps=100):
    infectious_percentages = [] # Per guardar el percentatge de infecciosos
    nodes = graph.nodes()
    num_initial_infectious = int(len(nodes) * initial_infectious) # Nombre de nodes inicials infectats
    initial_nodes_infectious = np.random.choice(nodes, num_initial_infectious, replace=False) # Bibliografia: [Ref.41]
    nodes_states = {}
    triangles = find_triangles_s2(graph)
    for node in nodes: 
        if node in initial_nodes_infectious:
            nodes_states[node] = 1 # Si el node està a la llista de infectats inicials -> Estat 1 (Infecciós)
        else:
            nodes_states[node] = 0
    infectious_percentages.append(sum(nodes_states.values()) / len(nodes))
    for step in range(time_steps):
        for node in nodes:
            # -- Si es susceptible es pot infectar --
            if nodes_states[node] == 0:
                infectious_by_simplex1 = 0
                infectious_by_simplex2 = 0
                # - Cas simplex 1 -
                for neighbor in graph.neighbors(node):
                    if nodes_states[neighbor] == 1: # Si el vei es infecciós pot infectar al susceptible
                        infectious_by_simplex1 += 1
                # - Cas simplex 2 - # Bibliograifa: [Ref.31] -> Ús 2
                triangles_for_node = []
                for triangle in triangles:
                    if node in triangle:
                        triangles_for_node.append(triangle)
                for triangle in triangles_for_node:
                    if triangle[0] == node:
                        if nodes_states[triangle[1]] == 1 and nodes_states[triangle[2]] == 1:
                            infectious_by_simplex2 += 1
                    elif triangle[1] == node:
                        if nodes_states[triangle[0]] == 1 and nodes_states[triangle[2]] == 1:
                            infectious_by_simplex2 += 1
                    elif triangle[2] == node:
                        if nodes_states[triangle[0]] == 1 and nodes_states[triangle[1]] == 1:
                            infectious_by_simplex2 += 1
                # - Calcul probabilitat combinada - # Bibliografia: [Ref.37] i [Ref.38] i [Ref.39]
                prob_infect = 1 - (((1 - beta1) ** infectious_by_simplex1) * ((1 - beta2) ** infectious_by_simplex2))
                # - Prendre decisió infeccio -
                if prob_infect > np.random.rand():
                    nodes_states[node] = 1
            # -- Si és infeccios es pot curar --
            elif nodes_states[node] == 1:
                if np.random.rand() < mu:
                    nodes_states[node] = 0
        # - Càlcul densitat infecciosos -
        infectious_percentages.append((1 / len(nodes)) * sum(nodes_states.values()))
    return infectious_percentages
In [24]:
# -- RSC --
from itertools import combinations # Per generar combinacions de 3 nodes en el moment de afegir els triangles al RSC
N = 100
p1 = 0.7
p_delta = 0.6
rsc_graph = nx.Graph()
rsc_graph.add_nodes_from([node for node in range(N)])
for node in rsc_graph.nodes():
    # - Afegir simplex-1 -
    potential_node_to_connect = node
    while potential_node_to_connect == node: # Per evitar connectar-se amb si mateix
        potential_node_to_connect = np.random.choice(rsc_graph.nodes(), 1)
    if np.random.rand() < p1:
        rsc_graph.add_edge(node, potential_node_to_connect[0])

for i, j, k in combinations(list(rsc_graph.nodes()), 3): # Bibliografia: [Ref.42]
    prob = np.random.rand()
    if rsc_graph.has_edge(i, j) and prob < p_delta:
        rsc_graph.add_edge(i, k)
        rsc_graph.add_edge(k, j)
    if rsc_graph.has_edge(i, k) and prob < p_delta:
        rsc_graph.add_edge(i, j)
        rsc_graph.add_edge(k, j)
    if rsc_graph.has_edge(j, k) and prob < p_delta:
        rsc_graph.add_edge(i, j)
        rsc_graph.add_edge(k, i)
In [25]:
test_scm = scm_order_2(rsc_graph, 0.1, 0.3, 0.2)
print(test_scm)
[0.1, 0.97, 0.8200000000000001, 0.86, 0.8, 0.8200000000000001, 0.78, 0.8200000000000001, 0.74, 0.78, 0.84, 0.8300000000000001, 0.8300000000000001, 0.84, 0.8, 0.75, 0.86, 0.79, 0.85, 0.8300000000000001, 0.8200000000000001, 0.86, 0.85, 0.85, 0.77, 0.74, 0.85, 0.77, 0.85, 0.87, 0.85, 0.8300000000000001, 0.84, 0.84, 0.8200000000000001, 0.8300000000000001, 0.8200000000000001, 0.86, 0.77, 0.86, 0.75, 0.9, 0.85, 0.85, 0.89, 0.85, 0.85, 0.73, 0.9, 0.8300000000000001, 0.78, 0.87, 0.86, 0.78, 0.89, 0.85, 0.81, 0.8200000000000001, 0.84, 0.84, 0.71, 0.88, 0.8200000000000001, 0.84, 0.79, 0.92, 0.76, 0.89, 0.8200000000000001, 0.78, 0.88, 0.8300000000000001, 0.8300000000000001, 0.8200000000000001, 0.8300000000000001, 0.85, 0.86, 0.8200000000000001, 0.79, 0.9, 0.8, 0.81, 0.84, 0.79, 0.76, 0.91, 0.85, 0.88, 0.79, 0.85, 0.8, 0.87, 0.86, 0.84, 0.86, 0.8300000000000001, 0.87, 0.8200000000000001, 0.89, 0.9, 0.84]

Referències externes:

[Ref.37] -- PIM. PEQUEÑO INSTITUTO MATEMÁTICAS 2023-2024 [en línia]. 26 d'abril, 10, 17 i 24 de maig [consulta: 10 de desembre de 2025]. Disponible a: https://www.icmat.es/PIM/wp-content/uploads/2024/04/Hoja_Probabilidad_Mercurio-Venus.pdf -->Informe que explica diversos conceptes de probabilitat.

[Ref.38] -- Sucesos complementarios y probabilidad complementaria [en línia][consulta: 10 de desembre de 2025]. Disponible a: https://sigmalitika.hirusta.io/termino/sucesos-complementarios-y-probabilidad-complementaria/ --> Web que explica com calcular la probabilitat del succés complementari.

[Ref.39] -- SOROLLA BARDAJÍ, Jordi. Introducció a la matemàtica. Lloc de publicació no disponible. Auto-editor,2013. ISBN 9788461648542 --> Llibre del doctor en matemàtiques de la Universitat de Lleida Jordi Sorolla.

[Ref.40] -- find_cliques [en línia][consulta: 10 de desembre de 2025]. Disponible a: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.clique.find_cliques.html --> Documentació oficial de la funció per a trobar els cliques d'un graf.

[Ref.41] -- numpy.random.choice [en línia][consulta: 10 de desembre de 2025]. Disponible a: https://numpy.org/doc/stable/reference/random/generated/numpy.random.choice.html --> Documentació oficial de la funció per fer seleccions aleatòries d'un array.

[Ref.42] -- Generar combinaciones específicas en Python [en línia][consulta: 10 de desembre de 2025]. Disponible a: --> Fil d'StackOverflow que explica com generar combinacions de 3 elements.

Exercici 2: Recreació Figura 3 (2,25 punts)

A partir del codi desenvolupat a la pregunta anterior, i amb la informació que tens a l’article proposat, recrea la Figura 3 del mateix. Aquesta conté dues visualitzacions, que són:

(a) Prevalença vs paràmetre d’infectivitat.

(b) Dinàmica temporal en una regió biestable amb diverses condicions inicials.

Nota: Pots variar alguns aspectes per reduir el cost computacional. Si és el cas, explica quins has modificat i el possible efecte que això pot haver causat en els resultats.

IMPORTANT

Malauradament, aquest exercici no ha estat resolt exitosament.

In [26]:
# -- Graphic 1 --
N = 2000
k = 20
k_delta = 6
mu = 1.0
lambda_values = [round(value, 1) for value in np.arange(0.0, 2.0, 0.1)] # round() per evitar nombres del tipus 1.00000000001 # Bibliografia: [Ref.43]
lambda_delta1 = 0.0
lambda_delta2 = 0.8
lambda_delta3 = 2.5
# -- Generar RSC --
rsc = nx.Graph()
rsc.add_nodes_from([node for node in range(N)])
p1 = (k - (2 * k_delta)) / ((N - 1) - (2 * k_delta))
p_delta = (2 * k_delta) / ((N - 1) * (N - 2))
for i, j in combinations(list(rsc.nodes()), 2):
    # - Simplex 1 -
    if np.random.rand() < p1:
        rsc.add_edge(i, j)
# - Simplex 2 -
for i, j, k in combinations(list(rsc.nodes()), 3): # Bibliografia: [Ref.31] -> ús 3
    if np.random.rand() < p_delta:
        if rsc.has_edge(i, j):
            rsc.add_edge(i, k)
            rsc.add_edge(j, k)
        elif rsc.has_edge(i, k):
            rsc.add_edge(i, j)
            rsc.add_edge(k, j)
        elif rsc.has_edge(j, k):
            rsc.add_edge(i, j)
            rsc.add_edge(i, k)
        else: # Cas extraordinari on cap dels tres nodes te cap aresta que els uneixi
            rsc.add_edge(i, j)
            rsc.add_edge(i, k)
            rsc.add_edge(j, k)
In [41]:
# -- Simulació per a gràfic 1 --
# - Lambda delta = 0.0 -
print("Computing case lambda_delta = 0.0")
results_labda_delta1 = []
for lambda_value in lambda_values:
    # lambda = beta * k / mu ==> beta = lamda * mu / k
    beta1 = (lambda_value * mu) / k
    beta2 = (lambda_delta1 * mu) / k_delta
    scm = scm_order_2(rsc, beta1, beta2, mu, initial_infectious=0.01, time_steps=200) # Bibliografia: [Ref.31] -> Ús 4
    results_labda_delta1.append(np.mean(scm[-100:])) # Bibliografia: [Ref.44] i [Ref.31] -> Ús 4
# - Lambda delta = 0.8 -
print("Computing case lambda_delta = 0.8")
results_labda_delta2 = []
for lambda_value in lambda_values:
    # lambda = beta * k / mu ==> beta = lamda * mu / k
    beta1 = (lambda_value * mu) / k
    beta2 = (lambda_delta2 * mu) / k_delta
    scm = scm_order_2(rsc, beta1, beta2, mu, initial_infectious=0.01, time_steps=200) # Bibliografia: [Ref.31] -> Ús 4
    results_labda_delta2.append(np.mean(scm[-100:])) # Bibliografia: [Ref.44] i [Ref.31] -> Ús 4
# - Lambda delta = 2.5 -
print("Computing case lambda_delta = 2.5")
results_labda_delta3 = []
for lambda_value in lambda_values:
    # lambda = beta * k / mu ==> beta = lamda * mu / k
    beta1 = (lambda_value * mu) / k
    beta2 = (lambda_delta3 * mu) / k_delta
    scm = scm_order_2(rsc, beta1, beta2, mu, initial_infectious=0.01, time_steps=200) # Bibliografia: [Ref.31] -> Ús 4
    results_labda_delta3.append(np.mean(scm[-100:])) # Bibliografia: [Ref.44] i [Ref.31] -> Ús 4
Computing case lambda_delta = 0.0
Computing case lambda_delta = 0.8
Computing case lambda_delta = 2.5
----------------------------------------------- Correccions introduides en la cèl·la anterior ( # Bibliografia: [Ref.31] -> Ús 4): -----------------------------------------------
  • scm = scm_order_2(rsc, beta1, beta2, mu, time_steps=1000) -> S'han posat més time_steps. Segons explica l'eina 100 passos (els per defecte) son massa pocs.

  • results_labda_delta3.append(np.mean(scm[-100:])) -> Es calcula la mitjana nomes dels ultims 100 passos. Segons explica l'eina, com la densitat d'infecciosos inicial es molt petita, això fa que les densitats d'infecciosos en les primeres estapes (les $p_{i}(t)$ de les primeres etapes) de la simulació siguin tambe molt baixes i si es calcula la mitjana de tota la simulació, les densitats d'infecciosos dels steps inicials faràn que la mitjana disminueixi molt.

In [31]:
# -- Càlculs gràfic 2 --
t = 500
initial_infectius = [round(value, 1) for value in np.arange(0.0, 1.0, 0.05)] # Taxes inicials d'infecciosos
lambda_value = 0.75
lambda_delta_value = 2.5
mu = 1.0
# lambda = beta * k / mu ==> beta = lamda * mu / k
beta = (lambda_value * mu) / k
beta_delta = (lambda_delta_value * mu) / k_delta
results = {} # Mappeig {infecciosos_inicials: resultats_scm}
for intitial in initial_infectius:
    res = scm_order_2(rsc, beta, beta_delta, mu, initial_infectious=intitial, time_steps=t)
    results[intitial] = res
In [44]:
t_range = [t for t in range(501)]
fig, ax = plt.subplots(1,2, figsize=(15,15))
fig.suptitle("Gràfics de densitat d'infectats vs lambda i densitat d'infectats vs. temps", fontsize=20)
ax[0].plot(lambda_values, results_labda_delta1, 'bo', label='lambda_delta = 0')
ax[0].plot(lambda_values, results_labda_delta2, 'ks', label='lambda_delta = 0.8')
ax[0].plot(lambda_values, results_labda_delta3, 'go', label='lambda_delta = 2.5')
ax[0].set_title("Densitat d'infectats vs lambda", fontsize=10)
ax[0].legend()
ax[0].set_ylabel("Density of infected")
ax[0].set_xlabel("Lambda")
cmap = plt.cm.viridis
norm = plt.Normalize(vmin=0.0, vmax=1.0)
for initial_infect, result in results.items():
    ax[1].plot(t_range, result, color=cmap(norm(initial_infect)))
ax[1].set_title("Densitat d'infectats vs temps", fontsize=10)
ax[1].set_ylabel("Density of infected")
ax[1].set_xlabel("Temps")
plt.show()
No description has been provided for this image

Referències externes:

[Ref.43] -- Python - range() for Float Numbers [en línia][consulta: 11 de desembre de 2025]. Disponible a: https://www.geeksforgeeks.org/python/python-range-for-float-numbers/ --> Web que explica com fer un range() però amb nombres de tipus float.

[Ref.44] -- numpy.mean [en línia][consulta: 11 de desembre de 2025]. Disponible a: https://numpy.org/doc/2.2/reference/generated/numpy.mean.html --> Documentació oficial de la funció per calcular la mitjana aritmètica.